/*
 *  Merge Sort(Top-down)
 *
 *  Promotion tips:
 *  1. cutoff to insertion sort
 *  2. compare mid and mid+1 before merge
 *  3. use auxiliary array
 */

package algs4.sort;

import java.util.Random;

public class Merge
{
    private static final int CUTOFF = 10;

    public static void sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];

        System.arraycopy(a, 0, aux, 0, n);

        sort(aux, a, 0, n - 1);
    }

    public static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
        // Cutoff to insertion sort
        if (hi <= lo + CUTOFF) {
            insertionSort(dst, lo, hi);
            return;
        }

        int mid = (lo + hi) / 2;
        sort(dst, src, lo, mid);
        sort(dst, src, mid + 1, hi);
        // Whether it is necessary to merge
        if (src[mid].compareTo(src[mid+1]) > 0)
            merge(src, dst, lo, mid, hi);
        else
            System.arraycopy(src, lo, dst, lo, hi - lo + 1);
    }

    private static void insertionSort(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) {
            int j;
            Comparable v = a[i];
            for (j = i; j > lo && v.compareTo(a[j-1]) < 0; j--)
                a[j] = a[j-1];
            a[j] = v;
        }
    }

    private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid , int hi) {
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                      dst[k] = src[j++];
            else if (j > hi)                       dst[k] = src[i++];
            else if (src[i].compareTo(src[j]) < 0) dst[k] = src[i++];
            else                                   dst[k] = src[j++];
        }

        // The following version is slower than above, why?
        /*int k = lo;
        while (i <= mid && j <= hi)
            if (src[i].compareTo(src[j]) < 0)
                dst[k++] = src[i++];
            else
                dst[k++] = src[j++];

        while (i <= mid) dst[k++] = src[i++];
        while (j <= hi)  dst[k++] = src[j++];*/
    }

    private static void show(Comparable[] a) {
        for (Comparable i : a)
            System.out.print(i + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.out.println("Usage: Command N");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);;

        // Build random array of integer
        Integer[] a   = new Integer[n];
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < n; i++)
            a[i] = random.nextInt(n);

        System.out.print("BF: "); show(a);
        sort(a);
        System.out.print("AF: "); show(a);
    }
}
